package com.example.kick.leetcode;

import org.springframework.boot.origin.Origin;
import org.springframework.util.comparator.Comparators;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * 基本算法练习
 */
public class BasicAlgorithmPractise {

    private static Map<Integer, Integer> stepMap = new HashMap<>();

    /**
     * 爬楼梯-递归实现
     * 注:每次最多走两个台阶
     *
     * @param destNumber 目标楼层数
     * @return
     */
    public static int climbStairsRecursive(int destNumber) {
        if (destNumber == 1) {
            return 1;
        }
        //当只有两个台阶时,可以每次走1个台阶,也可以一下走两个台阶,所以一共有两种走法
        if (destNumber == 2) {
            return 2;
        }
        Integer climbedSteps = stepMap.get(destNumber);
        if (null != climbedSteps) {
            return climbedSteps;
        } else {
            //递归实现,即若要走完当前台阶数,可转换成必须得先走完上1个以及上上1个台阶
            int currentSteps = climbStairsRecursive(destNumber - 1) + climbStairsRecursive(destNumber - 2);
            stepMap.put(destNumber, currentSteps);
            return currentSteps;
        }
    }

    /**
     * 爬楼梯-循环实现
     * 核心思想: 台阶数按自然行走路线,即由低到高,那么要走完当前台阶,就相当于必须得先走完上1个台阶以及上上1个台阶.因为本题的前提是每次最多走两个台阶
     * 注:每次最多走两个台阶
     *
     * @param destNumber
     * @return
     */
    public static int climbStairsWithLoop(int destNumber) {
        if (destNumber == 1) {
            return 1;
        }
        if (destNumber == 2) {
            return 2;
        }
        int previous = 2;
        int beforePrevious = 1;
        int result = 0;
        for (int i = 3; i <= destNumber; i++) {
            result = previous + beforePrevious;
            beforePrevious = previous;
            previous = result;
        }
        return result;
    }

    /**
     * 利用stream api对数组进行倒序排列
     *
     * @param origin
     * @return
     */
    public static int[] removeZeroToLast(int[] origin) {
        List<Integer> list = Arrays.stream(origin).boxed().collect(Collectors.toList());
        list.sort(Comparator.comparing(Integer::valueOf, Comparator.reverseOrder()));
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

    /**
     * 从数组中找出重复的数字,并存入新数组中,和原数组一起加入到集合中返回
     * @param origin
     * @return
     */
    public static List<int[]> findDuplicatedNumbers(int[] origin) {
        List<int[]> result = new ArrayList<>();
        result.add(origin);
        Map<Integer, Integer> countMap = new HashMap<>();
        List<Integer> extraList = new ArrayList<>();
        for (int number : origin) {
            Integer count = countMap.get(number);
            if (null == count) {
                countMap.put(number, 1);
            } else {
                countMap.put(number, count + 1);
                if (count == 1) {
                    extraList.add(number);
                }
            }
        }
        if (!extraList.isEmpty()) {
            result.add(extraList.stream().mapToInt(Integer::valueOf).toArray());
        }
        return result;
    }

    /**
     * 利用数组中的数字值与对应的下标关系,对数字进行+n操作后,再遍历数组,若数字的值不大于n,则说明此数字的下标+1即为缺失的数字.
     * 注:+n操作后,为获取数组中的原数值,需对n进行求余操作.比如数组{4,3,2,7,8,2,3,1},对数组中的第1个数4进行下标减1后,在数组中对应的数字为7,7+8=15,所以origin[3]由7变成了15.
     * 当循环到index=3时,为获取原数值7,需要对15进行求余操作,即15%8=7.
     * @param origin
     * @return
     */
    public static List<Integer> findDispearedNumbers(int[] origin) {
        int n = origin.length;
        for (int number : origin) {
            //对数组长度进行求余,以获取原数值.
            int x= (number - 1)%n;
            System.out.print(number+","+x+"; ");
            origin[x] += n;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (origin[i] <= n) {
                result.add(i + 1);
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        int steps1 = climbStairsRecursive(6);
//        int steps2 = climbStairsWithLoop(6);
//        System.out.println(steps1 + "," + steps2);

//        int[] array = {1, 0, 3, 0, 8};
//        int[] resultArray = removeZeroToLast(array);
//        for (int number : resultArray) {
//            System.out.print(number + ",");
//        }
        int[] array = {4,3,2,7,8,2,3,1};
//        List<int[]> result = findDuplicatedNumbers(array1);
//        for (int[] numbers : result) {
//            for (int i = 0; i < numbers.length; i++) {
//                System.out.print(numbers[i] + ",");
//            }
//            System.out.println();
//        }

        List<Integer> list = findDispearedNumbers(array);
        list.stream().forEach(System.out::println);
    }

}
